There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3 Output: 12 Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
Example 2:
Input: cardPoints = [2,2,2], k = 2 Output: 4 Explanation: Regardless of which two cards you take, your score will always be 4.
Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7 Output: 55 Explanation: You have to take all the cards. Your score is the sum of points of all cards.
Example 4:
Input: cardPoints = [1,1000,1], k = 1 Output: 1 Explanation: You cannot take the card in the middle. Your best score is 1.
Example 5:
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3 Output: 202
Constraints:
1 <= cardPoints.length <= 1051 <= cardPoints[i] <= 1041 <= k <= cardPoints.length
Average Rating: 4.97 (34 votes)
Solution
Overview
The brute force solution is to find all valid combinations of cards and then select the combination that gives us the maximum sum. To accomplish this, we can use a recursive approach. At each point, we choose a card either from the beginning or from the end of the array. Our base condition is when k cards are selected or when no cards are left to be selected.
This solution results in TLE because it checks an exponential number of combinations (many of the same combinations would be checked more than once).
We can optimize this solution by using a dynamic programming approach.
A key observation in this problem is that we need to select k cards from the beginning or end of the array. Thus no matter how many cards we choose from the beginning, in the end, we need to select two subarrays: one from the beginning, and one from the end, and their total lengths must be k (the only exception is when k = cardPoints.length, in that case, we'll select all cards). Thus after selecting the two arrays we will be left with a single subarray of length cardPoints.length - k. There are three ways we can select the cards:
- Select all cards from the beginning.
- Select all cards from the end.
- Select some cards from the beginning and the rest from the end.
In all the above three cases we will be left with a subarray (in the end, in the beginning, or somewhere in the middle) after our selection. This can be better understood in the following illustration where we are selecting 3 cards from an array of 8 cards.
Figure 1. An example demonstrating some of the positions of the subarrays possible from selecting k = 3 cards from the array.
In addition to the dynamic programming approach, we can also take a sliding window approach. A sliding window is a standard programming pattern used in many problems, including those related to finding the sum or the product of a subarray. In case you are not familiar with sliding windows, you can go through this article written by one of our LeetCode users: Sliding Window Problems for Beginners. In this article, we'll start by looking at the dynamic programming approach and discuss how to optimize its space complexity. After that, we will finish with the sliding window approach.
Approach 1: Dynamic Programming
Intuition
As we determined above, the k cards that we choose will form two contiguous subarrays: one at the start, and one at the end of the input array. If we choose i cards from the start (where i <= k) then we must choose k - i cards from the end. There are k different lengths the first array could be.
Since these k arrays are overlapping, we can calculate the prefix sum for each of the first k values, and then for each of the last k values (working from the end of the array, and going inwards). We will store these values in two arrays of size k.
We can then use these to efficiently check each possible way of selecting i cards from the start and k - i cards from the end.
Algorithm
-
Initialize two arrays of size
k + 1, namelyfrontSetOfCardsandrearSetOfCardsto store the score (prefix sums) obtained by selecting the firsticards and the lasticards in the array. -
We calculate the prefix sum (sum of
0 <= i <= kcards) for the firstkcardsfrontSetOfCards[i + 1] = frontSetOfCards[i] + cardPoints[i]and the lastkcardsrearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]. -
Initialize
maxScoreto 0. -
Iterate from
i = 0 -> k. At each iteration, we determine the possible score by selectingicards from the beginning of the array andk - icards from the end (currentScore). If this score is greater than themaxScorethen we update it.
Implementation
Complexity Analysis
Let k be the number of cards we need to select.
-
Time complexity: O(k). Here we are using two
forloops of lengthkto calculate the maximum possible score. This gives us O(2⋅k), which in Big O notation is equal to O(k). -
Space complexity: O(k). Here we are using two arrays to store the total score obtained by selecting i(0<=i<k) cards from the beginning and i cards from the end. This gives us O(2⋅k), which is equal to O(k).
Approach 2: Dynamic Programming - Space Optimized
Intuition
In approach 1 we used two extra storage spaces (two arrays of size k) to store the total score that can be obtained by taking i cards from the respective end of the array.
Instead of pre-computing the arrays, we can calculate the total score while iterating over the array and store the total score in two variables (in place of the two arrays).
Algorithm
-
Initialize two variables, namely
frontScoreandrearScoreto store the score obtained by selecting the firsticards and the lastk - icards in the array. -
frontScoreis initialized to the sum of the firstkcards in the array, andrearScoreis initialized to0. -
Initialize
maxScoretofrontScore. -
Iterate backwards from
i = k - 1 -> 0. At each iteration, we calculate the score by selectingicards from the beginning of the array andk - icards from the end (currentScore). If this score is greater thanmaxScore, we update it.
Implementation
Complexity Analysis
Let k be the number of cards we need to select.
-
Time complexity: O(k). We are using two
forloops of lengthkfor calculation purposes. This gives us O(2⋅k), which in Big O notation is equal to O(k). -
Space complexity: O(1). No extra space is used since all the calculations are done impromptu.
Approach 3: Sliding Window
Intuition
In this problem, we must draw exactly k cards from the array in such a way that the score (sum of the cards) is maximized. After drawing k cards from the array cardPoints.length - k cards will remain in the array.
Another way that we could view the problem is that our objective is to choose cards from the beginning or end of the array in such a way that the sum of the remaining cards is minimized.
We can use a sliding window to find the subarray of size cardPoints.length - k that has the minimal sum. Subtracting this value from the total sum of all the cards will give us our answer. This is because no matter where the minimum subarray is located (in the beginning, the middle, or the end) the remaining cards must be selected under the given rule: in one step, you can take one card from the beginning or the end of the array.
Algorithm
-
Find the sum of all cards in the array and store it in a variable
totalScore. -
If
kis equal tocardPoints.length, thenreturn totalScore. -
Initialize
requiredSubarrayLengthtocardPoints.length - k. -
Initialize two variables:
presentSubarrayScoreandstartingIndexto0. ThisstartingIndexmarks the starting point of the subarray presently under consideration. Thus it keeps track of the length of the present subarray. -
Initialize a variable
minSubarrayScoretototalScore. When the algorithm completes, this variable will hold the smallest possible subarray score in the input array. -
Iterate over the array.
- At each iteration add the current card to
presentSubarrayScore.
- At each iteration add the current card to
-
If the size of the subarray under consideration
presentSubarrayLengthis equal to therequiredSubarrayLength:- Compare the score of the subarray
presentSubarrayScorewith theminSubarrayScoreand modify theminSubarrayScoreso that it stores the minimum possible subarray sum. - Subtract the current card from the
presentSubarrayScore. - Increment the
startingIndex.
- Compare the score of the subarray
-
Subtract the
minSubarrayScorefrom thetotalScoreto get the maximum total score that can be obtained by pickingkcards from the beginning or the end of the array. Return this value.
Implementation
Complexity Analysis
Let n be the number of cards we need to select.
-
Time complexity: O(n). In the problem, we are iterating over the array of cards twice. So the time complexity will be O(2⋅n) = O(n).
-
Space complexity: O(1) since no extra space is required.
Finally, a solution that uses sensible variable names. I don't get why this is rampant. I was so used to it from Leetcode that I got a critical review in one interview because of this.
It just makes it easier to understand code without much explanation that useless shorth variable names look so ugly.
April 22, 2021 11:29 PM
One of the better-written solutions on LC. Nice!
I know the backtracking approach gets TLE, but for this post (and similar posts) would it be possible to have it as an approach and show the code? It's just I'm starting see that every problem can be solved recursively and it would be good to how its done :)
Last Edit: May 11, 2021 1:16 PM
This problem benefits from an implementation in Python, a language more expressive when dealing with stream processing, for example, the sliding window approach is quite terse :
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
s = sum(cardPoints)
window = sum(cardPoints[:(len(cardPoints)-k)])
r =s -window
for i in range(k):
window+=cardPoints[i+len(cardPoints)-k] -cardPoints[i]
r= max(r,s -window)
return r
May 5, 2021 6:22 AM
Java solution O(k) with explanation
public int maxScore(int[] nums, int k) {
int sum = 0;
int left = 0;
int right = k - 1;
// init the base case which starts from 0 ... k - 1
for (int i = 0; i < k; i++){
sum += nums[i];
}
if (k == nums.length){ // early return as there is only one solution
return sum;
}
// recognize that this is fixed length window that wraps around end of array
// e.x. [a, b, c, d, e, f, g] and k = 3
// can take at most between e, f, g ("negative array") to a, b, c, (positive array)
int newSum = sum; // save the initial state sum (from 0 .. k-1) for comparison
for (int i = 0; i < k; i++){
// do a rotation
newSum -= nums[right]; // remove element from end of positive array which is always >= 0
right--;
// add element from the beginning, which is always "negative"
left --;
newSum += nums[nums.length + left];
sum = Math.max(newSum, sum);
}
return sum;
}
In my solution if I use the for loop as the following way it works correctly: int z = cardPoints.size() - k;
for(int i = cardPoints.size() - 1; i >= z; i--){
However, in the following way, although the testcase work correctly, submission gives an error:
for(int i = cardPoints.size() - 1; i >= cardPoints.size() - k; i--){
error occurs because "i" may become negative which should not be happen.
Why this is happening can someone explain?
The Sliding Window is good to understand! Here is my Python version code:
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
totalScore = sum(cardPoints)
if k == len(cardPoints):
return totalScore
reqLen = len(cardPoints) - k
idx = 0
curScore = 0
minScore = totalScore
for i in range(len(cardPoints)):
curScore += cardPoints[i]
curLen = i - idx + 1
if curLen == reqLen:
minScore = min(minScore, curScore)
curScore -= cardPoints[idx]
idx += 1
return totalScore - minScore
Java solution O(k)
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
int sum=0, answer=0;
for(int i=0;i<k;i++){
sum += cardPoints[i];
}
answer = sum;
for(int i=k-1,j=n-1;i>=0 && j>=n-k;i--,j--){
sum -= cardPoints[i];
sum += cardPoints[j];
answer = Math.max(answer, sum);
}
return answer;
}We can calculate sum of the minimum widnow and array elements in one go:-
var maxScore = function(cardPoints, k) {
/*In every possible ans there will be a continues window of the size cardPoints.length-k for which we will not collect the points. We need to check that window of the size cardPoints.length-k with the having minimum sum.
Then we can remove this minimu sum of the windown from total array sum. This will be our answer.
*/
let windowSize=cardPoints.length-k,arrSum=0,minWindowSum=Number.MAX_SAFE_INTEGER,windowSum=0;
for(let i=0;i<cardPoints.length;i++){
arrSum+=cardPoints[i];
if(i<=windowSize-1){
windowSum+=cardPoints[i];
}else{
windowSum+=cardPoints[i];
windowSum-=cardPoints[i-windowSize];
}
if(i>=windowSize-1){
minWindowSum = Math.min(minWindowSum,windowSum);
}
}
return arrSum-minWindowSum;
}
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/25/2021 13:09 | Accepted | 56 ms | 42.4 MB | cpp |
| 05/25/2021 12:58 | Time Limit Exceeded | N/A | N/A | cpp |
| 05/11/2021 18:57 | Accepted | 52 ms | 45.8 MB | cpp |
| 05/11/2021 18:55 | Wrong Answer | N/A | N/A | cpp |
| 05/02/2020 16:57 | Wrong Answer | N/A | N/A | cpp |
| 05/02/2020 16:55 | Wrong Answer | N/A | N/A | cpp |
| 05/02/2020 16:49 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: // first take k elements from right, and then try to replace int maxScore(vector<int>& cardPoints, int k) { int n = cardPoints.size(); int res = 0, sum = 0; for(int i=n-k; i<n;i++) sum += cardPoints[i]; res = sum; for(int i=0;i<k;i++) { sum -= cardPoints[n-k+i]; sum += cardPoints[i]; res = max(res, sum); } return res; }};
